package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         662,
		Discription: "二叉树的同层最大宽度（中间夹着的nil也算）",
		Level:       2,
		Labels: map[string]int{
			"二叉树":  1,
			"层序遍历": 1,
		},
	})
}

type NodeInex struct {
	Index int
	Node  *ds.TreeNode
}

// WidthOfBinaryTree 正常层序遍历，每个节点和自己在完全二叉树中的索引对应，每遍历一层计算最左和最右节点的索引差值+1
//  @param root
//  @return int
func WidthOfBinaryTree(root *ds.TreeNode) int {
	q := []*NodeInex{{
		Node:  root,
		Index: 0,
	}}
	maxWidth := 0

	for len(q) != 0 {
		left := q[0].Index
		right := q[len(q)-1].Index
		maxWidth = max(maxWidth, right-left+1)

		length := len(q)
		for i := 0; i < length; i++ {
			node := q[i].Node
			index := q[i].Index
			if node.Left != nil {
				q = append(q, &NodeInex{
					Node:  node.Left,
					Index: 2*index + 1,
				})
			}
			if node.Right != nil {
				q = append(q, &NodeInex{
					Node:  node.Right,
					Index: 2*index + 2,
				})
			}
		}

		q = q[length:]
	}

	return maxWidth
}
